'''
Created on 07.11.2012

@author: felix_000
'''
from game.datastructure.PlayerColor import PlayerColor
import time

actions = [[0, -1], [-1, -1], [-1, 0], 
           [1, 0],  [1, 1],   [0, 1]]

#SWAP_ACTION = -1
WIN_LENGTH = 5

'''
is there a win from that position?
'''
def won(field, position):
    if getJustMaxLen(field, position, WIN_LENGTH) >= WIN_LENGTH:
        return True
    return None

def switchDirection(action):
    return [action[i] * -1 for i in xrange(len(action))]

def getMaxLen(field, color, minLen, possibleMinLen):
    # count the lengths of connected same colored points
    # direction of the connection is important
    # check it for diagonal, horizontal and vertical
    visited = set()
    bestPair = None
    for y in xrange(field.height):
        for x in xrange(field.width):
            if inRange(field, (x,y)) and field.get(x,y) == color and (x,y) not in visited:
                possibleMaxPair = getMaxLenFromPoint(field, (x,y), minLen, possibleMinLen)
                if possibleMaxPair is not None:
                    possibleMaxLen, action = possibleMaxPair
                    if possibleMaxLen >= minLen:
                        minLen = possibleMaxLen
                        bestPair = (minLen, action, (x,y))
    return bestPair

def getMaxLenFromPoint(field, position, minLen, minExpandable):
    x,y = position
    color = field.get(x,y)
    maxPair = None
    bestExpandable = -1
    for a in xrange(len(actions)/2):
        action = actions[a]
        colorlength = countLen(field, position, action, color)
        expandablelength = numExpendableInDirection(field, position, action, color)
        action = switchDirection(action)
        expandablelength += numExpendableInDirection(field, position, action, color)
        nx = x + action[0]
        ny = y + action[1]
        colorlength = colorlength + countLen(field, (nx,ny), action, color)
        if (expandablelength+colorlength) >= minExpandable and (colorlength > minLen or (colorlength == minLen and expandablelength > bestExpandable)):
            maxPair = (colorlength, action)
            minLen = colorlength
            bestExpandable = expandablelength
    return maxPair

def getJustMaxLen(field, position, minLen):
    x,y = position
    color = field.get(x,y)
    minLen -= 1
    for a in xrange(len(actions)/2):
        action = actions[a]
        colorlength = countLen(field, position, action, color)
        action = switchDirection(action)
        nx = x + action[0]
        ny = y + action[1]
        colorlength += countLen(field, (nx,ny), action, color)
        if colorlength > minLen:
            minLen = colorlength
    return minLen

def countLen(field, position, action, color, visited=None):
    if visited is None:
        visited = set()
    x,y = position
    colorlength = 0
    while inRange(field, (x, y)) and field.get(x, y) == color and ((x,y) not in visited):
        visited.add((x,y))
        colorlength = colorlength + 1
        x = x + action[0]
        y = y + action[1]
    return colorlength

def getNeighbours(field, position):
    x,y = position
    neighbours = set()
    for action in actions:
        nx = x + action[0]
        ny = y + action[1]
        if inRange(field, (nx, ny)):
            neighbours.add((nx,ny))
    return neighbours

def removeFromField(field, positions):
    for position in positions:
        x,y = position
        field.place(PlayerColor.NONE, x, y, True)

'''
returns the winning color and applys all actions on the field (removing captured
points).
Winning Color can be PlayerColor.BLACK, PlayerColor.WHITE or PlayerColor.NONE
'''
def applyAction(field, position, color):
    neighbours = getNeighbours(field, position)
    for neighbour in neighbours:
        x,y = neighbour
        if field.get(x,y) == color * -1:
            visited = set()
            if isSuicide(field, (x,y), color * -1, set(), visited):
                removeFromField(field, visited)
    
    return won(field, position)

def isSuicide(field, position, pcolor, visited=None, samecolorvisited=None):
    if visited is None:
        visited = set()
    if samecolorvisited is None:
        samecolorvisited = set()
    # it's suicide, when stone would be surrounded by enemy colors and
    # there is on freedom left
    toVisit = set()
    toVisit.add(position)
    while toVisit:
        position = toVisit.pop()
        visited.add(position)
        samecolorvisited.add(position)
        neighbours = getNeighbours(field, position)
        neighbours = neighbours.difference(visited)
        if len(neighbours) == 0:
            return True
        for neighbour in neighbours:
            nx,ny = neighbour
            color = field.get(nx, ny)
            if color == PlayerColor.NONE:
                return False
            elif color != pcolor:
                visited.add(neighbour)
            elif color == pcolor:
                toVisit.add((nx,ny))
    return True

def inRange(field, position):
    x,y = position
    return y >= 0 and y < field.height and x >= 0 and x < field.width and (field.get(x,y) is not None)

def isAllowed(field, position, color, visited=None):
#    x,y = position
#    allowed = False
#    if inRange(field, position):
#        allowed = field.get(x, y) == PlayerColor.NONE
#        if color is not None:
#            #start = time.time()
#            #for i in range(1000):
#            allowed = allowed and not isSuicide(field, position, color, visited)
#            #print "SUI",(time.time()-start)/1000.
#                
#    return allowed
    x,y = position
    # special case if stone is surrounded by same colored stones, it can be an unsaved suicide move
    
    allowed = inRange(field, position) and field.get(x,y) == PlayerColor.NONE and field.notallowed[y][x] != color
    if not allowed:
        return False
    neighbours = getNeighbours(field, position)
    special = True
    for neighbour in neighbours:
        x,y = neighbour
        if field.get(x,y) != color:
            special = False
            break
        
    if special:
        allowed = allowed and (not isSuicide(field, position, color))
    return allowed
def getAllowedFields(field, color):
#    visited = set()
#    allowed = list()
#    for y in range(field.height):
#        for x in range(field.width):
#            if isAllowed(field, (x,y), color, visited):
#                allowed.append((x,y))
#            visited.discard((x,y))
#    return allowed
    allowed = list()
    for y in xrange(field.height):
        for x in xrange(field.width):
            if isAllowed(field, (x,y), color):
                allowed.append((x,y))
    return allowed

def isExpendableInLine(field, position, action, color, possibleMinLen, visited=None):
    if visited is None:
        visited = set()
    expendable = numExpendableInDirection(field, position, action, color, visited)
    action = switchDirection(action)
    position = (position[0] + action[0], position[1] + action[1])
    expendable += numExpendableInDirection(field, position, action, color, visited)
    return expendable >= possibleMinLen

def numExpendableInDirection(field, position, action, color, visited=None):
    if visited is None:
        visited = set()
    x,y = position
    expendable = 0
    while inRange(field, (x,y)) and (field.get(x, y) == color or field.get(x,y) == PlayerColor.NONE):
        if field.get(x,y) == PlayerColor.NONE:
            expendable += 1
            visited.add((x,y))
        x += action[0]
        y += action[1]
    return expendable

def openedInTwoDirections(field, position, color, action, visited=None):
    if visited == None:
        visited = set()
    dir1 = isExpendableInLine(field, position, action, color, 1, visited)
    dir2 = isExpendableInLine(field, position, switchDirection(action), color, 1, visited)
    return dir1 and dir2

def getNeighboursOfSameColor(field, position, visited=None):
    if visited is None:
        visited = set()
    neighboursOfSameColor = set()
    sx, sy = position
    mycolor = field.get(sx, sy)
    toVisit = set()
    if position not in visited:
        toVisit.add(position)
    while len(toVisit) != 0:
        position = toVisit.pop()
        visited.add(position)
        neighboursOfSameColor.add(position)
        neighbours = getNeighbours(field, position)
        for neighbour in neighbours:
            x,y = neighbour
            if neighbour not in visited and field.get(x, y) == mycolor:
                toVisit.add(neighbour)
    return neighboursOfSameColor
